#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t;
void solve(){
	ll a,b,k;
	cin>>a>>b>>k;
	ll r=__gcd(a,b);
	if (max(a/r,b/r)<=k || max(a,b)<=k){
		cout<<1<<endl;
	}else  cout<<2<<endl;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>t;
	while(t--){
		solve();
	}	
	
	return 0;
}
